class Solution
{
    int k;
    void QuickSort(vector<vector<int>> &nums, int l, int r)
    {
        if(l >= r)
            return;

        int key = nums[rand() % (r - l + 1) + l][k];

        int i = l, left = l - 1, right = r + 1;

        while(i < right)
        {
            if(nums[i][k] > key)
                swap(nums[++left], nums[i++]);  // 按第 k 场考试分数从高到低完成对这些学生(矩阵中的行)的排序
            else if(nums[i][k] == key)
                i++;
            else
                swap(nums[--right], nums[i]);
        }

        // [l, left][left + 1, right - 1][right, r]
        //    < key           == key          > key
        QuickSort(nums, l, left);
        QuickSort(nums, right, r);
    }
public:
    vector<vector<int>> sortTheStudents(vector<vector<int>>& score, int k)
    {
        this->k = k;
        QuickSort(score, 0, score.size() - 1);
        return score;
    }
};